{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Edge Reversals So Every Node Is Reachable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minEdgeReversals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #可以到达每一个节点的最少边反转次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <code>n</code>&nbsp;个点的 <strong>简单有向图</strong>&nbsp;（没有重复边的有向图），节点编号为 <code>0</code>&nbsp;到 <code>n - 1</code>&nbsp;。如果这些边是双向边，那么这个图形成一棵&nbsp;<strong>树</strong>&nbsp;。</p>\n",
    "\n",
    "<p>给你一个整数&nbsp;<code>n</code>&nbsp;和一个 <strong>二维</strong>&nbsp;整数数组&nbsp;<code>edges</code>&nbsp;，其中&nbsp;<code>edges[i] = [u<sub>i</sub>, v<sub>i</sub>]</code>&nbsp;表示从节点&nbsp;<code>u<sub>i</sub></code>&nbsp;到节点&nbsp;<code>v<sub>i</sub></code>&nbsp;有一条&nbsp;<strong>有向边</strong>&nbsp;。</p>\n",
    "\n",
    "<p><strong>边反转</strong>&nbsp;指的是将一条边的方向反转，也就是说一条从节点&nbsp;<code>u<sub>i</sub></code>&nbsp;到节点&nbsp;<code>v<sub>i</sub></code>&nbsp;的边会变为一条从节点&nbsp;<code>v<sub>i</sub></code>&nbsp;到节点&nbsp;<code>u<sub>i</sub></code>&nbsp;的边。</p>\n",
    "\n",
    "<p>对于范围&nbsp;<code>[0, n - 1]</code>&nbsp;中的每一个节点 <code>i</code>&nbsp;，你的任务是分别 <strong>独立</strong> 计算 <strong>最少</strong>&nbsp;需要多少次 <strong>边反转</strong>&nbsp;，从节点 <code>i</code>&nbsp;出发经过 <strong>一系列有向边</strong>&nbsp;，可以到达所有的节点。</p>\n",
    "\n",
    "<p>请你返回一个长度为 <code>n</code>&nbsp;的整数数组<em>&nbsp;</em><code>answer</code><em>&nbsp;</em>，其中<em>&nbsp;</em><code>answer[i]</code>表示从节点&nbsp;<code>i</code>&nbsp;出发，可以到达所有节点的&nbsp;<strong>最少边反转</strong>&nbsp;次数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<p><img height=\"246\" src=\"https://assets.leetcode.com/uploads/2023/08/26/image-20230826221104-3.png\" width=\"312\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 4, edges = [[2,0],[2,1],[1,3]]\n",
    "<b>输出：</b>[1,1,0,2]\n",
    "<b>解释：</b>上图表示了与输入对应的简单有向图。\n",
    "对于节点 0 ：反转 [2,0] ，从节点 0 出发可以到达所有节点。\n",
    "所以 answer[0] = 1 。\n",
    "对于节点 1 ：反转 [2,1] ，从节点 1 出发可以到达所有节点。\n",
    "所以 answer[1] = 1 。\n",
    "对于节点 2 ：不需要反转就可以从节点 2 出发到达所有节点。\n",
    "所以 answer[2] = 0 。\n",
    "对于节点 3 ：反转 [1,3] 和 [2,1] ，从节点 3 出发可以到达所有节点。\n",
    "所以 answer[3] = 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<p><img height=\"217\" src=\"https://assets.leetcode.com/uploads/2023/08/26/image-20230826225541-2.png\" width=\"322\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 3, edges = [[1,2],[2,0]]\n",
    "<b>输出：</b>[2,0,1]\n",
    "<b>解释：</b>上图表示了与输入对应的简单有向图。\n",
    "对于节点 0 ：反转 [2,0] 和 [1,2] ，从节点 0 出发可以到达所有节点。\n",
    "所以 answer[0] = 2 。\n",
    "对于节点 1 ：不需要反转就可以从节点 2 出发到达所有节点。\n",
    "所以 answer[1] = 0 。\n",
    "对于节点 2 ：反转 [1,2] ，从节点 2 出发可以到达所有节点。\n",
    "所以 answer[2] = 1 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>edges.length == n - 1</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= u<sub>i</sub> == edges[i][0] &lt; n</code></li>\n",
    "\t<li><code>0 &lt;= v<sub>i</sub> == edges[i][1] &lt; n</code></li>\n",
    "\t<li><code>u<sub>i</sub> != v<sub>i</sub></code></li>\n",
    "\t<li>输入保证如果边是双向边，可以得到一棵树。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-edge-reversals-so-every-node-is-reachable](https://leetcode.cn/problems/minimum-edge-reversals-so-every-node-is-reachable/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-edge-reversals-so-every-node-is-reachable](https://leetcode.cn/problems/minimum-edge-reversals-so-every-node-is-reachable/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4\\n[[2,0],[2,1],[1,3]]', '3\\n[[1,2],[2,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        s = set()\n",
    "        neighbors = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            s.add(u * n + v)\n",
    "            neighbors[u].append(v)\n",
    "            neighbors[v].append(u)\n",
    "        visited = [False] * n\n",
    "        ans = [0] * n\n",
    "        ans0 = 0\n",
    "        q = deque([0])\n",
    "        visited[0] = True\n",
    "        while len(q) > 0:\n",
    "            i = q.popleft()\n",
    "            for j in neighbors[i]:\n",
    "                if not visited[j]:\n",
    "                    q.append(j)\n",
    "                    visited[j] = True\n",
    "                    if (i * n + j) not in s:\n",
    "                        ans0 += 1\n",
    "                        ans[j] = ans[i] - 1\n",
    "                    else:\n",
    "                        ans0 += 0\n",
    "                        ans[j] = ans[i] + 1\n",
    "        for i in range(n):\n",
    "            ans[i] += ans0\n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        s = set()\n",
    "        for u,v  in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "            s.add((u, v))\n",
    "        f = [0] * n\n",
    "        fas = [-1] * n\n",
    "        order = []\n",
    "        q = deque([0])\n",
    "        while q:\n",
    "            u = q.popleft()\n",
    "            order.append(u)\n",
    "            for v in g[u]:\n",
    "                if v == fas[u]: continue\n",
    "                fas[v] = u\n",
    "                q.append(v)\n",
    "\n",
    "        for u in order[::-1]:\n",
    "            for v in g[u]:\n",
    "                if v == fas[u]: continue\n",
    "                f[u] += f[v] + int((v, u) in s)\n",
    "        for u in order:\n",
    "            for v in g[u]:\n",
    "                if v == fas[u]: continue\n",
    "                f[v] = f[u] + int((u, v) in s) - int((v, u) in s)\n",
    "        return f       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        ans = [0] * n\n",
    "        nxt_dict = [[] for _ in range(n)]\n",
    "        edge_set = set()\n",
    "        for x, y in edges:\n",
    "            edge_set.add((x, y))\n",
    "            nxt_dict[x].append(y)\n",
    "            nxt_dict[y].append(x)\n",
    "        visited = {0}\n",
    "        queue = deque([0])\n",
    "        count = 0\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for nxt in nxt_dict[cur]:\n",
    "                if nxt not in visited:\n",
    "                    if (cur, nxt) not in edge_set:\n",
    "                        count += 1\n",
    "                    visited.add(nxt)\n",
    "                    queue.append(nxt)\n",
    "        ans[0] = count\n",
    "        visited = {0}\n",
    "        queue = deque([0])\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for nxt in nxt_dict[cur]:\n",
    "                if nxt not in visited:\n",
    "                    if (cur, nxt) in edge_set:\n",
    "                        ans[nxt] = ans[cur] + 1\n",
    "                    else:\n",
    "                        ans[nxt] = ans[cur] - 1\n",
    "                    visited.add(nxt)\n",
    "                    queue.append(nxt)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        d = set()\n",
    "        g = [[] for i in range(n)]\n",
    "        for i, j in edges:\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "            d.add((i, j))\n",
    "        \n",
    "        vis = set()\n",
    "        ans = [0] * n\n",
    "        queue = deque([0])\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            vis.add(node)\n",
    "            for i in g[node]:\n",
    "                if i not in vis:\n",
    "                    if (node, i) not in d:\n",
    "                        ans[0] += 1\n",
    "                    queue.append(i)\n",
    "\n",
    "        vis.clear()\n",
    "        queue = deque([0])\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            vis.add(node)\n",
    "            for i in g[node]:\n",
    "                if i not in vis:\n",
    "                    if (node, i) not in d:\n",
    "                        ans[i] = ans[node] - 1\n",
    "                    else:\n",
    "                        ans[i] = ans[node] + 1\n",
    "                    queue.append(i)\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DFS:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def gen_bfs_order_iteration(dct):\n",
    "        # 模板：生成深搜序即 dfs 序以及对应子树编号区间\n",
    "        n = len(dct)\n",
    "        order = 0\n",
    "        start = [-1] * n  # 每个原始节点的dfs序号开始点也是node_to_order\n",
    "        end = [-1]*n  # 每个原始节点的dfs序号结束点\n",
    "        parent = [-1]*n  # 每个原始节点的父节点\n",
    "        stack = [[0, -1]]\n",
    "        depth = [0]*n  # 每个原始节点的深度\n",
    "        order_to_node = [-1]*n  # 每个dfs序号对应的原始节点编号\n",
    "        while stack:\n",
    "            i, fa = stack.pop()\n",
    "            if i >= 0:\n",
    "                start[i] = order\n",
    "                order_to_node[order] = i\n",
    "                end[i] = order\n",
    "                order += 1\n",
    "                stack.append([~i, fa])\n",
    "                for j in dct[i]:\n",
    "                    if j != fa:  # 注意访问顺序可以进行调整，比如字典序逆序等等\n",
    "                        parent[j] = i\n",
    "                        depth[j] = depth[i] + 1\n",
    "                        stack.append([j, i])\n",
    "            else:\n",
    "                i = ~i\n",
    "                if parent[i] != -1:\n",
    "                    end[parent[i]] = end[i]\n",
    "\n",
    "        return start, end\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i, j in edges:\n",
    "            dct[i].append(j)\n",
    "            dct[j].append(i)\n",
    "        start, end = DFS().gen_bfs_order_iteration(dct)\n",
    "        diff = [0] * n\n",
    "        for i, j in edges:\n",
    "            if start[i] < start[j]:\n",
    "                a, b = start[j], end[j]\n",
    "                diff[a] += 1\n",
    "                if b + 1 < n:\n",
    "                    diff[b + 1] -= 1\n",
    "            else:\n",
    "                a, b = start[i], end[i]\n",
    "                if 0 <= a - 1:\n",
    "                    diff[0] += 1\n",
    "                    diff[a] -= 1\n",
    "                if b + 1 <= n - 1:\n",
    "                    diff[b + 1] += 1\n",
    "        diff = list(accumulate(diff))\n",
    "        return [diff[start[i]] for i in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DFS:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def gen_bfs_order_iteration(dct):\n",
    "        # 模板：生成深搜序即 dfs 序以及对应子树编号区间\n",
    "        n = len(dct)\n",
    "        for i in range(n):\n",
    "            dct[i].sort(reverse=True)  # 按照子节点编号从小到大进行遍历\n",
    "        order = 0\n",
    "        start = [-1] * n  # node_to_order\n",
    "        end = [-1] * n\n",
    "        parent = [-1] * n\n",
    "        stack = [[0, -1, 0]]\n",
    "        depth = [0] * n\n",
    "        order_to_node = [-1] * n\n",
    "        while stack:\n",
    "            i, fa, d = stack.pop()\n",
    "            if i >= 0:\n",
    "                start[i] = order\n",
    "                order_to_node[order] = i\n",
    "                end[i] = order\n",
    "                depth[i] = d\n",
    "                order += 1\n",
    "                stack.append([~i, fa, d])\n",
    "                for j in dct[i]:\n",
    "                    if j != fa:  # 注意访问顺序可以进行调整\n",
    "                        parent[j] = i\n",
    "                        stack.append([j, i, d + 1])\n",
    "            else:\n",
    "                i = ~i\n",
    "                if parent[i] != -1:\n",
    "                    end[parent[i]] = end[i]\n",
    "\n",
    "        return start, end\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i, j in edges:\n",
    "            dct[i].append(j)\n",
    "            dct[j].append(i)\n",
    "        start, end = DFS().gen_bfs_order_iteration(dct)\n",
    "        diff = [0] * n\n",
    "        for i, j in edges:\n",
    "            if start[i] < start[j]:\n",
    "                a, b = start[j], end[j]\n",
    "                diff[a] += 1\n",
    "                if b + 1 < n:\n",
    "                    diff[b + 1] -= 1\n",
    "            else:\n",
    "                a, b = start[i], end[i]\n",
    "                if 0 <= a - 1:\n",
    "                    diff[0] += 1\n",
    "                    diff[a] -= 1\n",
    "                if b + 1 <= n - 1:\n",
    "                    diff[b + 1] += 1\n",
    "        diff = list(accumulate(diff))\n",
    "        return [diff[start[i]] for i in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import defaultdict, Counter\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "# 给你一个 n 个点的 简单有向图 （没有重复边的有向图），节点编号为 0 到 n - 1 。如果这些边是双向边，那么这个图形成一棵 树 。\n",
    "\n",
    "# 给你一个整数 n 和一个 二维 整数数组 edges ，其中 edges[i] = [ui, vi] 表示从节点 ui 到节点 vi 有一条 有向边 。\n",
    "\n",
    "# 边反转 指的是将一条边的方向反转，也就是说一条从节点 ui 到节点 vi 的边会变为一条从节点 vi 到节点 ui 的边。\n",
    "\n",
    "# 对于范围 [0, n - 1] 中的每一个节点 i ，你的任务是分别 独立 计算 最少 需要多少次 边反转 ，从节点 i 出发经过 一系列有向边 ，可以到达所有的节点。\n",
    "\n",
    "# 请你返回一个长度为 n 的整数数组 answer ，其中 answer[i]表示从节点 i 出发，可以到达所有节点的 最少边反转 次数。\n",
    "from typing import Callable, Generic, List, TypeVar\n",
    "\n",
    "T = TypeVar(\"T\")\n",
    "\n",
    "\n",
    "class Rerooting(Generic[T]):\n",
    "    __slots__ = (\"adjList\", \"_n\", \"_decrement\")\n",
    "\n",
    "    def __init__(self, n: int, decrement: int = 0):\n",
    "        self.adjList = [[] for _ in range(n)]\n",
    "        self._n = n\n",
    "        self._decrement = decrement\n",
    "\n",
    "    def addEdge(self, u: int, v: int) -> None:\n",
    "        u -= self._decrement\n",
    "        v -= self._decrement\n",
    "        self.adjList[u].append(v)\n",
    "        self.adjList[v].append(u)\n",
    "\n",
    "    def rerooting(\n",
    "        self,\n",
    "        e: Callable[[int], T],\n",
    "        op: Callable[[T, T], T],\n",
    "        composition: Callable[[T, int, int, int], T],\n",
    "        root=0,\n",
    "    ) -> List[\"T\"]:\n",
    "        root -= self._decrement\n",
    "        assert 0 <= root < self._n\n",
    "        parents = [-1] * self._n\n",
    "        order = [root]\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            for next in self.adjList[cur]:\n",
    "                if next == parents[cur]:\n",
    "                    continue\n",
    "                parents[next] = cur\n",
    "                order.append(next)\n",
    "                stack.append(next)\n",
    "\n",
    "        dp1 = [e(i) for i in range(self._n)]\n",
    "        dp2 = [e(i) for i in range(self._n)]\n",
    "        for cur in order[::-1]:\n",
    "            res = e(cur)\n",
    "            for next in self.adjList[cur]:\n",
    "                if parents[cur] == next:\n",
    "                    continue\n",
    "                dp2[next] = res\n",
    "                res = op(res, composition(dp1[next], cur, next, 0))\n",
    "            res = e(cur)\n",
    "            for next in self.adjList[cur][::-1]:\n",
    "                if parents[cur] == next:\n",
    "                    continue\n",
    "                dp2[next] = op(res, dp2[next])\n",
    "                res = op(res, composition(dp1[next], cur, next, 0))\n",
    "            dp1[cur] = res\n",
    "\n",
    "        for newRoot in order[1:]:\n",
    "            parent = parents[newRoot]\n",
    "            dp2[newRoot] = composition(op(dp2[newRoot], dp2[parent]), parent, newRoot, 1)\n",
    "            dp1[newRoot] = op(dp1[newRoot], dp2[newRoot])\n",
    "        return dp1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        E = int\n",
    "\n",
    "        def e(root: int) -> E:\n",
    "            return 0\n",
    "\n",
    "        def op(childRes1: E, childRes2: E) -> E:\n",
    "            return childRes1 + childRes2\n",
    "\n",
    "        def composition(fromRes: E, parent: int, cur: int, direction: int) -> E:\n",
    "            \"\"\"direction: 0: cur -> parent, 1: parent -> cur\"\"\"\n",
    "            from_ = parent if direction == 0 else cur\n",
    "            to = cur if direction == 0 else parent\n",
    "            return fromRes + ((from_, to) not in ok)\n",
    "\n",
    "        R = Rerooting(n)\n",
    "        ok = set()\n",
    "        for u, v in edges:\n",
    "            R.addEdge(u, v)\n",
    "            ok.add((u, v))\n",
    "        dp = R.rerooting(e=e, op=op, composition=composition, root=0)\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        total = len(edges)+1\n",
    "        joint = [[] for i in range(total)]\n",
    "        graph = [set() for i in range(total)]\n",
    "        for u, v in edges:\n",
    "            graph[u].add(v)\n",
    "            joint[u].append(v)\n",
    "            joint[v].append(u)\n",
    "            \n",
    "            \n",
    "        # father = [-1 for i in range(total)]\n",
    "        # father_count = [0 for i in range(total)]\n",
    "        count = 0\n",
    "        \n",
    "        dfs = [n-1]\n",
    "        visited = [False for i in range(total)]\n",
    "        visited[n-1] = True\n",
    "        while len(dfs) != 0:\n",
    "            # print(dfs)\n",
    "            tmp = []\n",
    "            for node in dfs:\n",
    "                for x in joint[node]:\n",
    "                    if not visited[x]:\n",
    "                        tmp.append(x)\n",
    "                        if  x not in graph[node]:\n",
    "                            count += 1\n",
    "                        visited[x] = True\n",
    "            dfs = tmp\n",
    "            # print(dfs, count)\n",
    "            \n",
    "        \n",
    "        # print(count)\n",
    "        ans = [0 for i in range(n)]\n",
    "        ans[n-1] = count\n",
    "        dfs = [n-1]\n",
    "        visited = [False for i in range(total)]\n",
    "        visited[n-1] = True\n",
    "        while len(dfs) != 0:\n",
    "\n",
    "            tmp = []\n",
    "            for node in dfs:\n",
    "                for x in joint[node]:\n",
    "                    if not visited[x]:\n",
    "                        tmp.append(x)\n",
    "                        if x not in graph[node]:\n",
    "                            ans[x] = ans[node]-1\n",
    "                        else:\n",
    "                            ans[x] = ans[node]+1\n",
    "                        visited[x] = True\n",
    "            dfs = tmp\n",
    "            # print(dfs, ans)\n",
    "        \n",
    "        \n",
    "        return ans\n",
    "                        \n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            dct[x].append([y, 1])\n",
    "            dct[y].append([x, 0])\n",
    "\n",
    "        sub_cnt = [0] * n\n",
    "        sub_one = [0] * n\n",
    "        pre_cnt = [0] * n\n",
    "        pre_one = [0] * n\n",
    "        stack = [[0, -1]]\n",
    "        while stack:\n",
    "            x, fa = stack.pop()\n",
    "            if x >= 0:\n",
    "                stack.append([~x, fa])\n",
    "                for y, w in dct[x]:\n",
    "                    if y != fa:\n",
    "                        pre_cnt[y] = pre_cnt[x] + 1\n",
    "                        pre_one[y] = pre_one[x] + w\n",
    "                        stack.append([y, x])\n",
    "            else:\n",
    "                x = ~x\n",
    "                sub_cnt[x] = 1\n",
    "                for y, w in dct[x]:\n",
    "                    if y != fa:\n",
    "                        sub_cnt[x] += sub_cnt[y]\n",
    "                        sub_one[x] += sub_one[y] + w\n",
    "        ans = [pre_one[i] + (sub_cnt[i] - sub_one[i]) + (n - 1 - pre_cnt[i] - sub_cnt[i] - (sub_one[0] - sub_one[i] - pre_one[i])) for i in range(n)]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        ans = [0 for _ in range(n)]\n",
    "        g = [set() for _ in range(n)]\n",
    "        for u,v in edges:\n",
    "            g[u].add(v)\n",
    "            g[v].add(-u)\n",
    "        vis = {0:(0,0)}\n",
    "        q = [(0,0)]\n",
    "        step = 1\n",
    "        while q:\n",
    "            q1 = []\n",
    "            for u,cnt in q:\n",
    "                for v in g[u]:\n",
    "                    if v > 0 and v not in vis:\n",
    "                        q1.append((v,cnt))\n",
    "                        vis[v] = (step,cnt)\n",
    "                    if v < 0 and -v not in vis:\n",
    "                        q1.append((-v,cnt + 1))\n",
    "                        vis[-v] = (step,cnt + 1)\n",
    "                        ans[0] += 1\n",
    "            q = q1\n",
    "            step += 1\n",
    "        for i in range(1,n):\n",
    "            ans[i] = ans[0] + vis[i][0] - 2 * vis[i][1]\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        if n == 1: return [0]\n",
    "        sons = {}\n",
    "        fathers = {0:(-1,-1)}\n",
    "        for e in edges:\n",
    "            sons.setdefault(e[0], [])\n",
    "            sons[e[0]].append((e[1], 0))\n",
    "            sons.setdefault(e[1], [])\n",
    "            sons[e[1]].append((e[0], 1))\n",
    "        q = [0]\n",
    "        p = 0\n",
    "        # print(sons)\n",
    "        while p < len(q):\n",
    "            tmp = q[p]\n",
    "            p += 1\n",
    "            for stmp, relation in sons[tmp]:\n",
    "                if stmp != fathers[tmp][0]:\n",
    "                    q.append(stmp)\n",
    "                    fathers[stmp] = (tmp, relation)\n",
    "        root = 0\n",
    "        dp = {}\n",
    "        for node in q[::-1]:\n",
    "            dp[node] = 0\n",
    "            for son, score in sons[node]:\n",
    "                if son != fathers[node][0]:\n",
    "                    dp[node] += dp[son] + score\n",
    "        # print(sons)\n",
    "        # print(fathers)\n",
    "        # print(dp)\n",
    "        ans = [-1 for _ in range(n)]\n",
    "        pos = [0 for _ in range(n)]\n",
    "        ncalc = 0\n",
    "        while ncalc < n:\n",
    "            if ans[root] == -1:\n",
    "                ans[root] = dp[root]\n",
    "                # print(root)\n",
    "                ncalc += 1\n",
    "            if pos[root] < len(sons[root]):\n",
    "                son, relation = sons[root][pos[root]]\n",
    "                if son != fathers[root][0]:\n",
    "                    dp[root] -= relation + dp[son]\n",
    "                    dp[son] += dp[root] + (1 - relation)\n",
    "                    pos[root] += 1\n",
    "                    root = son\n",
    "                else:\n",
    "                    pos[root] += 1\n",
    "            else:\n",
    "                father, relation = fathers[root]\n",
    "                # print(root, father)\n",
    "                dp[root] -= dp[father] + (1 - relation)\n",
    "                dp[father] += dp[root] + relation\n",
    "                root = father\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # The graph would form a tree if its edges were bi-directional.\n",
    "        #联通图        \n",
    "        outd=defaultdict(list)\n",
    "        ind=defaultdict(list)\n",
    "        \n",
    "        for a,b in edges:\n",
    "            outd[a].append(b)\n",
    "            ind[b].append(a)\n",
    "        #form a tree rooted 0\n",
    "\n",
    "        child=defaultdict(list)\n",
    "        dfs=[0]\n",
    "        change=0\n",
    "        visit=set([0])\n",
    "        while dfs:\n",
    "            cur=dfs.pop()\n",
    "            for a in outd[cur]:\n",
    "                if a not in visit:\n",
    "                    visit.add(a)\n",
    "                    child[cur].append(a)\n",
    "                    dfs.append(a)\n",
    "            for b in ind[cur]:\n",
    "                if b not in visit:\n",
    "                    visit.add(b)\n",
    "                    change+=1\n",
    "                    child[cur].append(b)\n",
    "                    dfs.append(b)\n",
    "                \n",
    "        ans=[-1]*n\n",
    "        ans[0]=change\n",
    "        #walktree\n",
    "        dfs=[0]\n",
    "        while dfs:\n",
    "            node=dfs.pop()\n",
    "            for c in child[node]:\n",
    "                #if node->c\n",
    "                if c in outd[node]:\n",
    "                    ans[c]=ans[node]+1\n",
    "                else:\n",
    "                    ans[c]=ans[node]-1\n",
    "                dfs.append(c)\n",
    "        return ans   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Tree:\n",
    "    __slots__=(\"N\", \"index\", \"parent\", \"__mutable\",\n",
    "            \"root\", \"children\", \"depth\", \"tower\", \"upper_list\", \"des_count\", \"preorder_number\",\n",
    "            \"euler_vertex\", \"euler_edge\", \"in_time\", \"out_time\", \"lca_dst\",\n",
    "            \"hld_hedge\")\n",
    "\n",
    "    def __init__(self, N, index=0):\n",
    "        \"\"\" N 頂点 (index, index+1, ..., N-1+index) の根付き木を生成する. \"\"\"\n",
    "        self.N=N\n",
    "        self.index=index\n",
    "        self.parent=[-1]*(N+index)\n",
    "        self.__mutable=True\n",
    "\n",
    "    def vertex_exist(self, x):\n",
    "        \"\"\" 頂点 x が存在するかどうかを判定する. \"\"\"\n",
    "\n",
    "        return self.index<=x<self.index+self.N\n",
    "\n",
    "    def __after_seal_check(self,*vertexes):\n",
    "        \"\"\" 木が確定していて, vertexes の頂点が存在するかどうかをチェックする. \"\"\"\n",
    "\n",
    "        if self.__mutable:\n",
    "            return False\n",
    "\n",
    "        for v in vertexes:\n",
    "            if not self.vertex_exist(v):\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def is_mutable(self):\n",
    "        \"\"\" 木が確定して [いない] かどうかを返す. \"\"\"\n",
    "        return self.__mutable\n",
    "\n",
    "    #設定パート\n",
    "    def root_set(self, root):\n",
    "        \"\"\" 頂点 root を根に設定する.\"\"\"\n",
    "\n",
    "        assert self.vertex_exist(root)\n",
    "        assert self.__mutable\n",
    "\n",
    "        self.root=root\n",
    "\n",
    "    def parent_set(self,x,y):\n",
    "        \"\"\" 頂点 x の親を y に設定する.\"\"\"\n",
    "\n",
    "        assert self.vertex_exist(x)\n",
    "        assert self.vertex_exist(y)\n",
    "        assert self.__mutable\n",
    "\n",
    "        self.parent[x]=y\n",
    "\n",
    "    def child_set(self, x, y):\n",
    "        \"\"\" 頂点 x の子の一つに y を設定する (頂点 x の方が親).\"\"\"\n",
    "\n",
    "        assert self.vertex_exist(x)\n",
    "        assert self.vertex_exist(y)\n",
    "        assert self.__mutable\n",
    "\n",
    "        self.parent[y]=x\n",
    "\n",
    "    def seal(self):\n",
    "        \"\"\" 木の情報を確定させる (これ以降, 情報の変更は禁止).\"\"\"\n",
    "\n",
    "        assert self.__mutable\n",
    "        assert hasattr(self, \"root\")\n",
    "\n",
    "        a=self.index\n",
    "        b=self.index+self.N\n",
    "        C=[[] for _ in range(b)]\n",
    "\n",
    "        p=self.parent\n",
    "        ve=self.vertex_exist\n",
    "        for i in range(a,b):\n",
    "            if i!=self.root:\n",
    "                assert ve(p[i])\n",
    "                C[p[i]].append(i)\n",
    "\n",
    "        self.__mutable=False\n",
    "        self.children=C\n",
    "\n",
    "    #データを求める.\n",
    "    def depth_search(self, mode=True):\n",
    "        \"\"\" 木の深さを求める.\n",
    "\n",
    "        mode=True ならば, 各頂点の深さが記録されたリストを返す.\n",
    "        \"\"\"\n",
    "\n",
    "        assert self.__after_seal_check()\n",
    "\n",
    "        if hasattr(self, \"depth\"):\n",
    "            if mode:\n",
    "                return self.depth\n",
    "            else:\n",
    "                return\n",
    "\n",
    "        children = self.children\n",
    "        depth = [-1] * (self.index+self.N)\n",
    "        tower = [[] for _ in range(self.N)]\n",
    "\n",
    "        S = [self.root]\n",
    "        depth[self.root]=0\n",
    "        tower[0]=[self.root]\n",
    "\n",
    "        while S:\n",
    "            x = S.pop()\n",
    "            for y in children[x]:\n",
    "                depth[y] = depth[x] + 1\n",
    "                tower[depth[y]].append(y)\n",
    "                S.append(y)\n",
    "\n",
    "        self.depth = depth\n",
    "        self.tower = tower\n",
    "\n",
    "        if mode:\n",
    "            return depth\n",
    "\n",
    "    def vertex_depth(self, x):\n",
    "        \"\"\" 頂点 x の深さを求める.\"\"\"\n",
    "\n",
    "        assert self.__after_seal_check(x)\n",
    "\n",
    "        if not hasattr(self, \"depth\"):\n",
    "            self.depth_search(mode=False)\n",
    "        return self.depth[x]\n",
    "\n",
    "    def __upper_list(self):\n",
    "        assert self.__after_seal_check()\n",
    "\n",
    "        if hasattr(self, \"upper_list\"):\n",
    "            return\n",
    "\n",
    "        if not hasattr(self,\"depth\"):\n",
    "            self.depth_search(False)\n",
    "\n",
    "        b=max(self.depth).bit_length()\n",
    "        X=[[-1]*(self.index+self.N) for _ in range(b)]\n",
    "\n",
    "        Y=X[0]\n",
    "        p=self.parent\n",
    "\n",
    "        for x in range(self.index,self.index+self.N):\n",
    "            if x!=self.root:\n",
    "                Y[x]=p[x]\n",
    "            else:\n",
    "                Y[x]=self.root\n",
    "\n",
    "        for k in range(1,b):\n",
    "            Y=X[k-1]\n",
    "            Z=X[k]\n",
    "\n",
    "            for x in range(self.index,self.index+self.N):\n",
    "                Z[x]=Y[Y[x]]\n",
    "        self.upper_list=X\n",
    "\n",
    "    def upper(self, x, k, over=True):\n",
    "        \"\"\" 頂点 x から見て k 個親の頂点を求める.\n",
    "\n",
    "        over: (頂点 x の深さ)<k のときに True ならば根を返し, False ならばエラーを吐く.\n",
    "        \"\"\"\n",
    "\n",
    "        assert self.__after_seal_check(x)\n",
    "        assert 0<=k\n",
    "\n",
    "        if not hasattr(self,\"upper_list\"):\n",
    "            self.__upper_list()\n",
    "\n",
    "        if self.vertex_depth(x)<k:\n",
    "            if over:\n",
    "                return self.root\n",
    "            else:\n",
    "                raise ValueError\n",
    "\n",
    "        i=0\n",
    "        while k:\n",
    "            if k&1:\n",
    "                x=self.upper_list[i][x]\n",
    "            k>>=1\n",
    "            i+=1\n",
    "        return x\n",
    "\n",
    "    def lowest_common_ancestor_greedy(self, x, y):\n",
    "        \"\"\"頂点 x, y の最小共通先祖 (x,yに共通する先祖で最も深いもの) を \"愚直に\" 求める.\"\"\"\n",
    "\n",
    "        assert self.__after_seal_check(x,y)\n",
    "        dx=self.vertex_depth(x); dy=self.vertex_depth(y)\n",
    "\n",
    "        if dx<dy:\n",
    "            dx,dy=dy,dx\n",
    "            x,y=y,x\n",
    "\n",
    "        pa=self.parent\n",
    "        while dx>dy:\n",
    "            x=pa[x]\n",
    "            dx-=1\n",
    "\n",
    "        while x!=y:\n",
    "            x=pa[x]\n",
    "            y=pa[y]\n",
    "\n",
    "        return x\n",
    "\n",
    "    def __lca_prepare(self):\n",
    "        assert self.__after_seal_check()\n",
    "\n",
    "        N=self.N\n",
    "\n",
    "        bit=max(1, ((2*N-1)-1).bit_length())\n",
    "        D=[[0]*(2*N-1) for _ in range(bit)]\n",
    "\n",
    "        self.euler_tour_vertex()\n",
    "        tour=self.euler_vertex\n",
    "        D[0]=tour.copy()\n",
    "        dep=self.depth_search(True)\n",
    "\n",
    "        for i in range(1, bit):\n",
    "            shift=1<<i\n",
    "            tab=D[i]\n",
    "\n",
    "            for j in range(0, 2*N-1, 2*shift):\n",
    "                t=min(j+shift, 2*N-1)\n",
    "                tab[t-1]=tour[t-1]\n",
    "\n",
    "                for k in range(t-2, j-1, -1):\n",
    "                    if dep[tour[k]]<dep[tab[k+1]]:\n",
    "                        tab[k]=tour[k]\n",
    "                    else:\n",
    "                        tab[k]=tab[k+1]\n",
    "\n",
    "                if 2*N-1<=t:\n",
    "                    break\n",
    "\n",
    "                tab[t]=tour[t]\n",
    "                r=min(t+shift, 2*N-1)\n",
    "\n",
    "                for k in range(t+1, r):\n",
    "                    if dep[tab[k-1]]<dep[tour[k]]:\n",
    "                        tab[k]=tab[k-1]\n",
    "                    else:\n",
    "                        tab[k]=tour[k]\n",
    "\n",
    "        self.lca_dst=D\n",
    "        return\n",
    "\n",
    "    def lowest_common_ancestor(self, x, y):\n",
    "        \"\"\"頂点 x, y の最小共通先祖 (x,yに共通する先祖で最も深いもの) を \"高速に\" 求める. \"\"\"\n",
    "\n",
    "        assert self.__after_seal_check(x,y)\n",
    "        if not hasattr(self, \"lca_dst\"):\n",
    "            self.__lca_prepare()\n",
    "\n",
    "        a=self.in_time[x]; b=self.in_time[y]\n",
    "        if a>b:\n",
    "            x,y=y,x\n",
    "            a,b=b,a\n",
    "\n",
    "        if a==b:\n",
    "            return self.lca_dst[0][a]\n",
    "\n",
    "        p=(a^b).bit_length()-1\n",
    "        tab=self.lca_dst[p]\n",
    "        u=tab[a]; v=tab[b]\n",
    "\n",
    "        return u if self.vertex_depth(u)<self.vertex_depth(v) else v\n",
    "\n",
    "    def degree(self,v):\n",
    "        \"\"\" 頂点 v の次数を求める. \"\"\"\n",
    "\n",
    "        assert self.__after_seal_check(v)\n",
    "        if v==self.root:\n",
    "            return len(self.children[v])\n",
    "        else:\n",
    "            return len(self.children[v])+1\n",
    "\n",
    "    def diameter(self):\n",
    "        \"\"\" 木の直径を求める.\"\"\"\n",
    "\n",
    "        assert self.__after_seal_check()\n",
    "\n",
    "        from collections import deque\n",
    "        def bfs(start):\n",
    "            X=[-1]*(self.index+self.N)\n",
    "            Q=deque([start])\n",
    "            X[start]=0\n",
    "\n",
    "            pa=self.parent\n",
    "            ch=self.children\n",
    "            while Q:\n",
    "                x=Q.popleft()\n",
    "\n",
    "                if X[pa[x]]==-1:\n",
    "                    Q.append(pa[x])\n",
    "                    X[pa[x]]=X[x]+1\n",
    "\n",
    "                for y in ch[x]:\n",
    "                    if X[y]==-1:\n",
    "                        Q.append(y)\n",
    "                        X[y]=X[x]+1\n",
    "            y=max(range(self.index,self.index+self.N), key=lambda x:X[x])\n",
    "            return y,X[y]\n",
    "\n",
    "        y,_=bfs(self.root)\n",
    "        z,d=bfs(y)\n",
    "        return d,(y,z)\n",
    "\n",
    "    def path(self, u, v, faster=False):\n",
    "        \"\"\" 頂点 u, v 間のパスを求める. \"\"\"\n",
    "\n",
    "        assert self.__after_seal_check(u,v)\n",
    "\n",
    "        if faster:\n",
    "            w=self.lowest_common_ancestor(u,v)\n",
    "        else:\n",
    "            w=self.lowest_common_ancestor_greedy(u,v)\n",
    "\n",
    "        pa=self.parent\n",
    "        X=[u]\n",
    "        while u!=w:\n",
    "            u=pa[u]\n",
    "            X.append(u)\n",
    "\n",
    "        Y=[v]\n",
    "        while v!=w:\n",
    "            v=pa[v]\n",
    "            Y.append(v)\n",
    "        return X+Y[-2::-1]\n",
    "\n",
    "    def is_parent(self, u, v):\n",
    "        \"\"\" u は v の親か? \"\"\"\n",
    "\n",
    "        assert self.__after_seal_check(u,v)\n",
    "        return v!=self.root and u==self.parent[v]\n",
    "\n",
    "    def is_children(self, u, v):\n",
    "        \"\"\" u は v の子か? \"\"\"\n",
    "\n",
    "        assert self.__after_seal_check(u,v)\n",
    "        return self.is_parent(v,u)\n",
    "\n",
    "    def is_brother(self,u,v):\n",
    "        \"\"\" 2つの頂点 u, v は兄弟 (親が同じ) か?  \"\"\"\n",
    "\n",
    "        assert self.__after_seal_check(u,v)\n",
    "\n",
    "        if u==self.root or v==self.root:\n",
    "            return False\n",
    "        return self.parent[u]==self.parent[v]\n",
    "\n",
    "    def is_ancestor(self,u,v):\n",
    "        \"\"\" 頂点 u は頂点 v の先祖か? \"\"\"\n",
    "\n",
    "        assert self.__after_seal_check(u,v)\n",
    "\n",
    "        dd=self.vertex_depth(v)-self.vertex_depth(u)\n",
    "        if dd<0:\n",
    "            return False\n",
    "\n",
    "        v=self.upper(v,dd)\n",
    "        return u==v\n",
    "\n",
    "    def is_descendant(self,u,v):\n",
    "        \"\"\" 頂点 u は頂点 v の子孫か? \"\"\"\n",
    "\n",
    "        assert self.__after_seal_check(u,v)\n",
    "        return self.is_ancestor(v,u)\n",
    "\n",
    "    def direction(self, u, v):\n",
    "        \"\"\" 頂点 u から頂点 v (u!=v) へ向かうパスが頂点 u の次に通る頂点\"\"\"\n",
    "\n",
    "        assert self.__after_seal_check(u,v)\n",
    "        assert u!=v\n",
    "\n",
    "        if self.is_ancestor(u,v):\n",
    "            du=self.vertex_depth(u)\n",
    "            dv=self.vertex_depth(v)\n",
    "            return self.upper(v,dv-(du+1))\n",
    "        else:\n",
    "            return self.parent[u]\n",
    "\n",
    "    def jump(self, u, v, k, default=-1):\n",
    "        \"\"\" 頂点 u から頂点 v へ向かうパスにおいて k 番目 (0-indexed) に通る頂点 (パスの長さが k より大きい場合は default)\n",
    "\n",
    "        u: int\n",
    "        v: int\n",
    "        k: int\n",
    "        default=-1: int\n",
    "        \"\"\"\n",
    "\n",
    "        assert self.__after_seal_check(u,v)\n",
    "\n",
    "        if k==0:\n",
    "            return u\n",
    "\n",
    "        # lca を求める.\n",
    "        x=u; y=v\n",
    "        dx=self.vertex_depth(x); dy=self.vertex_depth(y)\n",
    "        if dx>dy:\n",
    "            x,y=y,x\n",
    "            dx,dy=dy,dx\n",
    "        y=self.upper(y, dy-dx)\n",
    "\n",
    "        if x==self.root or x==y:\n",
    "            w=x\n",
    "        else:\n",
    "            bit=dx.bit_length()\n",
    "\n",
    "            X=self.upper_list\n",
    "            for t in range(bit-1,-1,-1):\n",
    "                px=X[t][x]; py=X[t][y]\n",
    "                if px!=py:\n",
    "                    x=px; y=py\n",
    "            w=self.parent[x]\n",
    "\n",
    "        dist_uw=self.vertex_depth(u)-self.vertex_depth(w)\n",
    "        dist_wv=self.vertex_depth(v)-self.vertex_depth(w)\n",
    "\n",
    "        if dist_uw+dist_wv<k:\n",
    "            return default\n",
    "        elif k<=dist_uw:\n",
    "            return self.upper(u, k)\n",
    "        else:\n",
    "            return self.upper(v, (dist_uw+dist_wv)-k)\n",
    "\n",
    "    def is_leaf(self,v):\n",
    "        \"\"\" 頂点 v は葉? \"\"\"\n",
    "\n",
    "        return not bool(self.children[v])\n",
    "\n",
    "    def distance(self, u, v, faster=True):\n",
    "        \"\"\" 2頂点 u, v 間の距離を求める. \"\"\"\n",
    "\n",
    "        assert self.__after_seal_check(u,v)\n",
    "\n",
    "        dep=self.vertex_depth\n",
    "\n",
    "        if faster:\n",
    "            return dep(u)+dep(v)-2*dep(self.lowest_common_ancestor(u,v))\n",
    "        else:\n",
    "            return dep(u)+dep(v)-2*dep(self.lowest_common_ancestor_greedy(u,v))\n",
    "\n",
    "    def __descendant_count(self):\n",
    "        assert self.__after_seal_check()\n",
    "        if hasattr(self,\"des_count\"):\n",
    "            return\n",
    "\n",
    "        if not hasattr(self,\"tower\"):\n",
    "            self.depth_search(False)\n",
    "\n",
    "        self.des_count=[1]*(self.index+self.N)\n",
    "        pa=self.parent\n",
    "        for T in self.tower[:0:-1]:\n",
    "            for x in T:\n",
    "                self.des_count[pa[x]]+=self.des_count[x]\n",
    "        return\n",
    "\n",
    "    def descendant_count(self, v):\n",
    "        \"\"\" 頂点 v の子孫の数を求める. \"\"\"\n",
    "        assert self.__after_seal_check(v)\n",
    "        self.__descendant_count()\n",
    "        return self.des_count[v]\n",
    "\n",
    "    def subtree_size(self, v):\n",
    "        \"\"\" 頂点 v を根とした部分根付き木のサイズを求める. \"\"\"\n",
    "        return self.descendant_count(v)\n",
    "\n",
    "    def preorder(self,v):\n",
    "        \"\"\" 頂点 v の行きがけ順を求める. \"\"\"\n",
    "        assert self.__after_seal_check(v)\n",
    "        if hasattr(self, \"preorder_number\"):\n",
    "            self.preorder_number[v]\n",
    "\n",
    "        from collections import deque\n",
    "        Q=deque([self.root])\n",
    "        T=[-1]*(self.N+self.index)\n",
    "\n",
    "        p=1\n",
    "        while Q:\n",
    "            x=Q.popleft()\n",
    "            T[x]=p\n",
    "            p+=1\n",
    "\n",
    "            C=self.children[x]\n",
    "            for y in C:\n",
    "                Q.append(y)\n",
    "        self.preorder_number=T\n",
    "        return T[v]\n",
    "\n",
    "    def dfs_yielder(self, order=None):\n",
    "        \"\"\" DFS における頂点の出入りを yield する.\n",
    "\n",
    "        以下のような関数を (仮想的に) 実行する.\n",
    "\n",
    "        def dfs(v):\n",
    "            yield (v,1) #頂点 v に入る\n",
    "            for w in self.children[v]:\n",
    "                dfs(w) #頂点 v を出る.\n",
    "            yield (v,-1)\n",
    "\n",
    "        order (1変数関数): for w in self.children[v] の順番を指定する (昇順) (※ 無い場合は任意, 破壊的)\n",
    "        \"\"\"\n",
    "        assert self.__after_seal_check()\n",
    "\n",
    "        #最初\n",
    "        yield (self.root, 1)\n",
    "\n",
    "        v=self.root\n",
    "\n",
    "        ch=self.children\n",
    "        pa=self.parent\n",
    "\n",
    "        R=[-1]*self.index+[len(ch[x]) for x in range(self.index,self.index+self.N)]\n",
    "        S=[0]*(self.index+self.N)\n",
    "\n",
    "        if order!=None:\n",
    "            for w in range(self.index, self.index+self.N):\n",
    "                ch[w].sort(key=order)\n",
    "\n",
    "        while True:\n",
    "            if R[v]==S[v]:  #もし, 進めないならば\n",
    "                yield (v,-1) #頂点vを出る\n",
    "                if v==self.root:\n",
    "                    break\n",
    "                else:\n",
    "                    v=pa[v]\n",
    "            else:   #進める\n",
    "                w=v\n",
    "                v=ch[v][S[v]]\n",
    "                S[w]+=1\n",
    "                yield (v, 1)\n",
    "\n",
    "    def top_down(self):\n",
    "        \"\"\" 木の根から yield する. \"\"\"\n",
    "\n",
    "        assert self.__after_seal_check()\n",
    "        if not hasattr(self, \"tower\"):\n",
    "            self.depth_search(False)\n",
    "\n",
    "        for layer in self.tower:\n",
    "            yield from layer\n",
    "\n",
    "    def bottom_up(self):\n",
    "        \"\"\" 木の葉から yield する. \"\"\"\n",
    "\n",
    "        assert self.__after_seal_check()\n",
    "        if not hasattr(self, \"tower\"):\n",
    "            self.depth_search(False)\n",
    "\n",
    "        for layer in self.tower[::-1]:\n",
    "            yield from layer\n",
    "\n",
    "    def tree_dp_from_leaf(self, merge, unit, f, g, Mode=False):\n",
    "        \"\"\" 从叶子节点开始进行树 DP。\n",
    "    \n",
    "        [输入]\n",
    "        merge: 形成可交换单元的二元运算 M x M -> M\n",
    "        unit: M 的单位元\n",
    "        f: X x V x V → M: f(x,v,w): v 是父节点，w 是子节点\n",
    "        g: M x V → X: g(x,v)\n",
    "        Mode: False → 只返回根的值，True → 返回所有的值\n",
    "    \n",
    "        [补充]\n",
    "        当顶点 v 的孩子是 x,y,z,..., w 时，更新式是 * 为 merge 时，\n",
    "            dp[v]=g(f(dp[x],v,x)*f(dp[y],v,y)*f(dp[z],v,z)*...*f(dp[w],v,w), v)\n",
    "        \"\"\"\n",
    "        assert self.__after_seal_check()\n",
    "    \n",
    "        data = [unit] * (self.index + self.N)\n",
    "        ch = self.children\n",
    "    \n",
    "        for x in self.bottom_up():\n",
    "            for y in ch[x]:\n",
    "                data[x] = merge(data[x], f(data[y], x, y))\n",
    "            data[x] = g(data[x], x)\n",
    "    \n",
    "        if Mode:\n",
    "            return data\n",
    "        else:\n",
    "            return data[self.root]\n",
    "    \n",
    "    \n",
    "    def rerooting(self, merge, unit, f, g):\n",
    "        \"\"\" 进行树的换根 DP。\n",
    "    \n",
    "        [输入]\n",
    "        merge: 形成可交换单元的二元运算 M x M -> M\n",
    "        unit: M 的单位元\n",
    "        f: X x V x V → M: f(x,v,w): v 是父节点，w 是子节点\n",
    "        g: M x V → X: g(x,v)\n",
    "    \n",
    "        ※ tree_dp_from_leaf 和同样的形式\n",
    "    \n",
    "        [补充]\n",
    "        当顶点 v 的孩子是 x,y,z,..., w 时，更新式是 * 为 merge 时，\n",
    "            dp[v]=g(f(dp[x],v,x)*f(dp[y],v,y)*f(dp[z],v,z)*...*f(dp[w],v,w), v)\n",
    "        \"\"\"\n",
    "\n",
    "        assert self.__after_seal_check()\n",
    "\n",
    "        upper=[unit]*(self.index+self.N)\n",
    "        lower=[unit]*(self.index+self.N)\n",
    "\n",
    "        ch=self.children\n",
    "        pa=self.parent\n",
    "\n",
    "        #DFSパート\n",
    "        lower=self.tree_dp_from_leaf(merge, unit, f, g, True)\n",
    "\n",
    "        #BFSパート\n",
    "        for v in self.top_down():\n",
    "            cc=ch[v]\n",
    "\n",
    "            #累積マージ\n",
    "            deg=len(cc)\n",
    "\n",
    "            Left=[unit]; x=unit\n",
    "            for c in cc:\n",
    "                x=merge(x, f(lower[c], v, c))\n",
    "                Left.append(x)\n",
    "\n",
    "            Right=[unit]; y=unit\n",
    "            for c in cc[::-1]:\n",
    "                y=merge(y, f(lower[c], v, c))\n",
    "                Right.append(y)\n",
    "            Right=Right[::-1]\n",
    "\n",
    "            for i in range(deg):\n",
    "                c=cc[i]\n",
    "\n",
    "                a=merge(Left[i], Right[i+1])\n",
    "\n",
    "                if v!=self.root:\n",
    "                    b=merge(a, f(upper[v], v, pa[v]))\n",
    "                else:\n",
    "                    b=a\n",
    "\n",
    "                upper[c]=g(b, v)\n",
    "\n",
    "        A=[unit]*(self.index+self.N)\n",
    "        for v in range(self.index,self.index+self.N):\n",
    "            if v!=self.root:\n",
    "                a=f(upper[v], v, pa[v])\n",
    "            else:\n",
    "                a=unit\n",
    "\n",
    "            for c in ch[v]:\n",
    "                a=merge(a, f(lower[c], v, c))\n",
    "            A[v]=g(a, v)\n",
    "        return A\n",
    "\n",
    "def Making_Tree_from_Edges(N, E, root, index=0):\n",
    "    \"\"\" 辺のリストから木を作る.\n",
    "\n",
    "    N: 頂点数\n",
    "    E: 辺のリスト E=[(u[0],v[0]), ..., (u[N-2], v[N-2]) ]\n",
    "    root: 根\n",
    "    \"\"\"\n",
    "\n",
    "    from collections import deque\n",
    "\n",
    "    A=[[] for _ in range(N+index)]\n",
    "    for u,v in E:\n",
    "        A[u].append(v)\n",
    "        A[v].append(u)\n",
    "\n",
    "    T=Tree(N, index)\n",
    "    T.root_set(root)\n",
    "\n",
    "    S=[False]*(N+index); S[root]=True\n",
    "    Q=deque([root])\n",
    "    while Q:\n",
    "        v=Q.popleft()\n",
    "        for w in A[v]:\n",
    "            if not S[w]:\n",
    "                S[w]=True\n",
    "                T.parent_set(w,v)\n",
    "                Q.append(w)\n",
    "\n",
    "    T.seal()\n",
    "    return T\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        T = Making_Tree_from_Edges(n, edges, 0, 0)\n",
    "        graph = [set() for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            graph[u].add(v)\n",
    "\n",
    "        def merge(x, y):\n",
    "\n",
    "            return x + y\n",
    "\n",
    "        def f(x, v, w):\n",
    "\n",
    "            return x + int(w not in graph[v])\n",
    "\n",
    "        def g(x, v):\n",
    "\n",
    "            return x\n",
    "\n",
    "        res = T.rerooting(merge, 0, f, g)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        # 建立两个图\n",
    "        # - 有向图：dag\n",
    "        # - 无向图：udag\n",
    "        dag = defaultdict(set)\n",
    "        udag = defaultdict(set)\n",
    "        for u, v in edges:\n",
    "            dag[u].add(v)\n",
    "            udag[u].add(v)\n",
    "            udag[v].add(u)\n",
    "\n",
    "        ########## 换根DP 和 二次扫描/遍历 ##########\n",
    "        \n",
    "        # 1. DP 状态定义\n",
    "        # dp[u]: 从结点 u 出发，到达所有结点的最少边反转次数\n",
    "        # 或者，将有向图转变为 以结点 u 为根的有根树，所需的最少边反转次数\n",
    "        dp = [0] * n\n",
    "\n",
    "        # 2. DP 状态初始化\n",
    "        # dp[0]: 从结点 0 出发，达到所有结点的最少边反转次数\n",
    "        # 一次 BFS 扫描/遍历，计算 dp[0]，dp 状态初始化\n",
    "\n",
    "        que = deque()\n",
    "        que.append(0)\n",
    "\n",
    "        visited = set()\n",
    "        visited.add(0)\n",
    "\n",
    "        while que:\n",
    "            u = que.popleft()\n",
    "\n",
    "            for v in udag[u]:\n",
    "                if v not in visited:\n",
    "                    if v not in dag[u]:\n",
    "                        dp[0] += 1\n",
    "\n",
    "                    visited.add(v)\n",
    "                    que.append(v)\n",
    "\n",
    "        # 3. DP 状态转移\n",
    "        # 二次 BFS 扫描/遍历，DP 状态转移，计算所有 DP 状态 dp[u]\n",
    "\n",
    "        que.append(0)\n",
    "\n",
    "        visited.clear()\n",
    "        visited.add(0)\n",
    "\n",
    "        while que:\n",
    "            u = que.popleft()\n",
    "\n",
    "            for v in udag[u]:\n",
    "                if v not in visited:\n",
    "                    # 换根，DP 状态转移\n",
    "                    dp[v] = dp[u]\n",
    "                    if v in dag[u]:\n",
    "                        dp[v] += 1\n",
    "                    else:\n",
    "                        dp[v] -= 1\n",
    "\n",
    "                    visited.add(v)\n",
    "                    que.append(v)\n",
    "\n",
    "        return dp\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 记录每个点的边及方向\n",
    "        l_pe = [[] for _ in range(n)]\n",
    "\n",
    "        for i, (u, v) in enumerate(edges):\n",
    "            l_pe[u].append((i, True, v))\n",
    "            l_pe[v].append((i, False, u))\n",
    "\n",
    "        # 从最外层的点开始计算，对于每个点，计算每个边方向反转数，-1表示总反转数\n",
    "        ret = [defaultdict(int) for _ in range(n)]\n",
    "\n",
    "        # 记录每个点的当前边数量\n",
    "        l_enum = [0] * n\n",
    "\n",
    "        # 点边数的最小堆\n",
    "        l = []\n",
    "\n",
    "        for i, e in enumerate(l_pe):\n",
    "            l_enum[i] = len(e)\n",
    "            heapq.heappush(l, (len(e), i))\n",
    "\n",
    "        # 未处理过的点\n",
    "        undo = set(range(n))\n",
    "\n",
    "        while undo:\n",
    "            while 1:\n",
    "                _, u = heapq.heappop(l)\n",
    "                if u not in undo:\n",
    "                    continue\n",
    "\n",
    "                undo.remove(u)\n",
    "                break\n",
    "\n",
    "            for ei, f, v in l_pe[u]:\n",
    "                if v not in undo:\n",
    "                    continue\n",
    "\n",
    "                # v的边减1\n",
    "                l_enum[v] -= 1\n",
    "                heapq.heappush(l, (l_enum[v], v))\n",
    "\n",
    "                # 方向为u-v时需要加+1\n",
    "                ret[v][ei] = ret[u][-1] + f\n",
    "                ret[v][-1] += ret[v][ei]\n",
    "\n",
    "        # u为最后一个点，除u外其他点的向内的边都还没有计算（u没有向内的边）\n",
    "        dp = [u]\n",
    "\n",
    "        while dp:\n",
    "            u = dp.pop(0)\n",
    "\n",
    "            for ei, f, v in l_pe[u]:\n",
    "                if ei in ret[v]:\n",
    "                    continue\n",
    "\n",
    "                #方向为u-v时需要加上u向外点数量+1\n",
    "                ret[v][ei] = ret[u][-1] - ret[u][ei] + f\n",
    "                ret[v][-1] += ret[v][ei]\n",
    "                dp.append(v)\n",
    "\n",
    "        return [d[-1] for d in ret]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        adj = defaultdict(set)\n",
    "        radj = defaultdict(set)\n",
    "        for a, b in edges:\n",
    "            adj[a].add(b)\n",
    "            radj[b].add(a)\n",
    "        ans = defaultdict(int)\n",
    "        cost = 0\n",
    "        dq = deque([0])\n",
    "        seen = {0}\n",
    "        while dq:\n",
    "            i = dq.popleft()\n",
    "            for u in adj[i]:\n",
    "                if u not in seen:\n",
    "                    dq.append(u)\n",
    "                    seen.add(u)\n",
    "            for v in radj[i]:\n",
    "                if v not in seen:\n",
    "                    dq.append(v)\n",
    "                    seen.add(v)\n",
    "                    cost += 1\n",
    "        ans[0] = cost\n",
    "        dq = deque([0])\n",
    "        seen = {0}\n",
    "        while dq:\n",
    "            i = dq.popleft()\n",
    "            cost = ans[i]\n",
    "            for u in adj[i]:\n",
    "                if u not in seen:\n",
    "                    dq.append(u)\n",
    "                    ans[u] = cost + 1\n",
    "                    seen.add(u)\n",
    "            for v in radj[i]:\n",
    "                if v not in seen:\n",
    "                    dq.append(v)\n",
    "                    ans[v] = cost - 1\n",
    "                    seen.add(v)\n",
    "        ret = []\n",
    "        for i in range(n):\n",
    "            ret.append(ans[i])\n",
    "        return ret\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "### START ITERATE RECURSION ###\n",
    "from types import GeneratorType\n",
    "def bootstrap(f, stack=[]):\n",
    "    def wrappedfunc(*args, **kwargs):\n",
    "        if stack:\n",
    "            return f(*args, **kwargs)\n",
    "        else:\n",
    "            to = f(*args, **kwargs)\n",
    "            while True:\n",
    "                if type(to) is GeneratorType:\n",
    "                    stack.append(to)\n",
    "                    to = next(to)\n",
    "                else:\n",
    "                    stack.pop()\n",
    "                    if not stack:\n",
    "                        break\n",
    "                    to = stack[-1].send(to)\n",
    "            return to\n",
    " \n",
    "    return wrappedfunc\n",
    "#### END ITERATE RECURSION ####\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, es: List[List[int]]) -> List[int]:\n",
    "        # find root\n",
    "        edges = [[] for _ in range(n)]\n",
    "        for u, v in es:\n",
    "            edges[u].append((v, 0))\n",
    "            edges[v].append((u, 1))\n",
    "        root = 0\n",
    "        ans = [0] * n\n",
    "        dep = [0] * n\n",
    "        cnt = [0] * n\n",
    "        @bootstrap\n",
    "        def dfs(cur, ban):\n",
    "            ret = 0\n",
    "            for to, w in edges[cur]:\n",
    "                if to == ban:\n",
    "                    continue\n",
    "                dep[to] = dep[cur] + 1\n",
    "                cnt[to] = cnt[cur] + w\n",
    "                ret += yield dfs(to, cur)\n",
    "                ret += w\n",
    "            yield ret\n",
    "        ans[root] = dfs(root, -1)\n",
    "        for i in range(1, n):\n",
    "            ans[i] = dep[i] - 2 * cnt[i] + ans[root]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        ans = [0] * n\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        edges = {(x, y) for x, y in edges}\n",
    "        \n",
    "        def dfs(cur, parent):\n",
    "            ans[0] += (cur, parent) in edges\n",
    "            for i in g[cur]:\n",
    "                if i != parent:\n",
    "                    dfs(i, cur)\n",
    "\n",
    "        def reroot(cur, parent):\n",
    "            if (cur, parent) in edges:\n",
    "                ans[cur] = ans[parent] - 1\n",
    "            elif (parent, cur) in edges:\n",
    "                ans[cur] = ans[parent] + 1\n",
    "            for i in g[cur]:\n",
    "                if i != parent:\n",
    "                    reroot(i, cur)\n",
    "\n",
    "        dfs(0, -1)\n",
    "        reroot(0, -1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        self.graph = [[] for _ in range(n)]\n",
    "        # 1代表graph[a]到b,-1代表b到graph[a]\n",
    "        for x, y in edges:\n",
    "            self.graph[x].append((y,1))\n",
    "            self.graph[y].append((x, -1))\n",
    "        self.ans = [0]*n\n",
    "        # 首先计算出节点0的反转次数\n",
    "        self.cal(0, -1)\n",
    "        # 计算出其余节点反转次数的变化量\n",
    "        self.cal2(0, -1)\n",
    "        return self.ans\n",
    "\n",
    "    def cal(self, node, father):\n",
    "        for y, dire in self.graph[node]:\n",
    "            if y != father:\n",
    "                if dire == -1:\n",
    "                    self.ans[0] += 1\n",
    "                self.cal(y, node)\n",
    "            \n",
    "    def cal2(self, x, father):\n",
    "        # 若x->y, ans[y] = ans[x] + 1\n",
    "        # 若x<-y, ans[y] = ans[x] - 1\n",
    "        for y, dire in self.graph[x]:\n",
    "            if y != father:\n",
    "                if dire == 1:\n",
    "                    self.ans[y] = self.ans[x]+1\n",
    "                else:\n",
    "                    self.ans[y] = self.ans[x]-1\n",
    "                self.cal2(y, x)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            graph[u].append((v, 1))\n",
    "            graph[v].append((u, 0))\n",
    "        answer = [None] * n\n",
    "        base = 0\n",
    "        def dfs(x, p, d, revert):\n",
    "            nonlocal base\n",
    "            answer[x] = d - revert - revert\n",
    "            for b, w in graph[x]:\n",
    "                if b != p:\n",
    "                    base += 1 - w\n",
    "                    dfs(b, x, d + 1, revert + (1 - w))\n",
    "        dfs(0, None, 0, 0)\n",
    "        for i in range(n):\n",
    "            answer[i] += base\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "        #换根DP\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for u,v in edges:\n",
    "            g[u].append([v,1])\n",
    "            g[v].append([u,-1])\n",
    "        \n",
    "        ans = [0]*(n)\n",
    "\n",
    "        def dfs(u:int,fa:int) ->None:\n",
    "            for v,dir in g[u]:\n",
    "                if v!=fa:\n",
    "                    ans[0]+=dir<0\n",
    "                    dfs(v,u)\n",
    "        \n",
    "        dfs(0,-1)\n",
    "\n",
    "        def reroot(u:int,fa:int) ->None:\n",
    "            for v,dir in g[u]:\n",
    "                if v!=fa:\n",
    "                    ans[v] = ans[u]+dir\n",
    "                    reroot(v,u)\n",
    "        \n",
    "        reroot(0,-1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "\n",
    "        graph = collections.defaultdict(list)\n",
    "        edge_set = set()\n",
    "        for x,y in edges:\n",
    "            graph[x].append((y,1))\n",
    "            graph[y].append((x,-1))\n",
    "        \n",
    "        ans = [0]*n\n",
    "        def dfs(root,parent):\n",
    "\n",
    "            for node,direct in graph[root]:\n",
    "\n",
    "                if node==parent:\n",
    "                    continue \n",
    "                ans[0] += direct<0\n",
    "                dfs(node,root)\n",
    "            return \n",
    "        \n",
    "        dfs(0,-1)\n",
    "\n",
    "        def reroot(root,parent):\n",
    "\n",
    "            for node,direct in graph[root]:\n",
    "                if node==parent:\n",
    "                    continue \n",
    "                ans[node] += ans[root]+direct\n",
    "                reroot(node, root)\n",
    "            return \n",
    "        \n",
    "        reroot(0,-1)\n",
    "        return ans\n",
    "\n",
    "          \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append([b, 1])\n",
    "            graph[b].append([a, - 1])\n",
    "        res = [0] * n \n",
    "        def dfs(node, par):\n",
    "            for nei, d in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue \n",
    "                res[0] += d < 0\n",
    "                dfs(nei, node)\n",
    "        dfs(0, - 1)\n",
    "        def reRoot(node, par):\n",
    "            for nei, d in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue \n",
    "                res[nei] = res[node] + d \n",
    "                reRoot(nei, node)\n",
    "        reRoot(0, - 1)\n",
    "        return res \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        pos=collections.defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            pos[u].append([v,1])\n",
    "            pos[v].append([u,-1])\n",
    "            \n",
    "        ans=[0]*n#需要翻转的 \n",
    "     #   print(cnt)\n",
    "        def rootbuild(curr,fa):\n",
    "            res=0\n",
    "            for nei,dis in pos[curr]:\n",
    "                if nei!=fa:\n",
    "                    res+=rootbuild(nei, curr)+(dis<0)\n",
    "            return res  \n",
    "\n",
    "        ans[0]=rootbuild(0, -1)\n",
    "\n",
    "        def changeroot(curr,fa):\n",
    "            nonlocal ans\n",
    "            cv=ans[curr]  \n",
    "            for nei,dis in pos[curr]:\n",
    "                if nei!=fa:\n",
    "                    ans[nei]=cv+1 if dis>0 else cv-1\n",
    "                    changeroot(nei, curr) \n",
    "        changeroot(0, -1)   \n",
    "        return ans\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "        ad=defaultdict(list)\n",
    "        for s,e in edges:\n",
    "            ad[s].append([e,0])\n",
    "            ad[e].append([s,1])\n",
    "        ans=[0]*n \n",
    "        size=[1]*n\n",
    "        def dfs(cur,fa,d):\n",
    "            ans[0]+=d\n",
    "            for nex,nexd in ad[cur]:\n",
    "                if nex !=fa:\n",
    "                    dfs(nex,cur,nexd)\n",
    "                    size[cur]+=size[nex]\n",
    "        dfs(0,-1,0)\n",
    "        def reroot(cur,fa):\n",
    "            for nex,nexd in ad[cur]:\n",
    "                if nex !=fa:\n",
    "                    if nexd==0:\n",
    "                        ans[nex]=ans[cur]+1\n",
    "                    else:\n",
    "                        ans[nex]=ans[cur]-1\n",
    "                    reroot(nex,cur)\n",
    "       \n",
    "        reroot(0,-1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append([b, 1])\n",
    "            graph[b].append([a, - 1])\n",
    "        cnt = 0\n",
    "        def dfs(node, par):\n",
    "            nonlocal cnt \n",
    "            for nei, d in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue \n",
    "                cnt += d < 0 \n",
    "                dfs(nei, node)\n",
    "        dfs(0, - 1)\n",
    "        res = [0] * n \n",
    "        def reRoot(node, par, cnt):\n",
    "            res[node] = cnt \n",
    "            for nei, d in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue \n",
    "                reRoot(nei, node, cnt + d)\n",
    "        reRoot(0, - 1, cnt)\n",
    "        return res \n",
    "        \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        tree = [[] for _ in range(n)]\n",
    "        for item in edges:\n",
    "            tree[item[0]].append(((item[0], item[1]), 0))\n",
    "            tree[item[1]].append(((item[1], item[0]), 1))\n",
    "        ans = [0] * n\n",
    "        def dfs_first(cur, vst):\n",
    "            vst[cur] = True\n",
    "            for item, id in tree[cur]:\n",
    "                if vst[item[1]]:\n",
    "                    continue\n",
    "                if id == 1:\n",
    "                    ans[0] += 1\n",
    "                dfs_first(item[1], vst)\n",
    "        def dfs_second(cur, shun, father, vst):\n",
    "            vst[cur] = True\n",
    "            ans[cur] = ans[father] - 1 if shun else ans[father] + 1\n",
    "            for item, id in tree[cur]:\n",
    "                if vst[item[1]]:\n",
    "                    continue\n",
    "                dfs_second(item[1], id, cur, vst)\n",
    "        vst = [False] * n\n",
    "        dfs_first(0, vst)\n",
    "        vst = [False] * n\n",
    "        vst[0] = True\n",
    "        for item, id in tree[0]:\n",
    "            dfs_second(item[1], id, 0, vst)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        t=defaultdict(list)\n",
    "        r=defaultdict(list)\n",
    "        for a,b in edges:\n",
    "            t[a].append(b)\n",
    "            r[b].append(a)\n",
    "        \n",
    "        in_=[0]*n\n",
    "        out_=[0]*n\n",
    "        \n",
    "        \n",
    "        vis=set()\n",
    "        def dfs(node):\n",
    "            vis.add(node)\n",
    "            for x in t[node]:\n",
    "                if x not in vis:\n",
    "                    dfs(x)\n",
    "                    in_[node]+=in_[x]\n",
    "                    out_[node]+=out_[x]+1\n",
    "            for x in r[node]:\n",
    "                if x not in vis:\n",
    "                    dfs(x)\n",
    "                    in_[node]+=in_[x]+1\n",
    "                    out_[node]+=out_[x]\n",
    "        dfs(0)\n",
    "        \n",
    "        vis=set()\n",
    "        res=[0]*n\n",
    "        def cal(node):\n",
    "            vis.add(node)\n",
    "            res[node]=in_[node]\n",
    "            for x in t[node]:\n",
    "                if x not in vis:\n",
    "                    in_[x]=in_[node]+1\n",
    "                    out_[x]=out_[node]-1\n",
    "                    cal(x)\n",
    "            for x in r[node]:\n",
    "                if x not in vis:\n",
    "                    out_[x]=out_[node]+1\n",
    "                    in_[x]=in_[node]-1\n",
    "                    cal(x)\n",
    "        cal(0)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = defaultdict(set)\n",
    "        for a, b in edges:\n",
    "            g[a].add((b, 1))\n",
    "            g[b].add((a, -1))\n",
    "\n",
    "        dp = [0] * n\n",
    "        def init(node, pre):\n",
    "            for n, dir in g[node]:\n",
    "                if n == pre: continue\n",
    "                dp[0] += 1 if dir < 0 else 0\n",
    "                init(n, node)\n",
    "\n",
    "        init(0, -1)\n",
    "\n",
    "        def dfs(node, pre):\n",
    "            for n, dir in g[node]:\n",
    "                if n == pre: continue\n",
    "                dp[n] = dp[node] + dir\n",
    "                dfs(n, node)\n",
    "        \n",
    "        dfs(0, -1)\n",
    "        return dp\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        children = defaultdict(list)\n",
    "        children_reverse = defaultdict(list)\n",
    "        for src, dst in edges:\n",
    "            children[src].append(dst)\n",
    "            children_reverse[dst].append(src)\n",
    "        \n",
    "        cache, cost = {}, 0\n",
    "        def dfs(root: int, parent: int, path: List[int]):\n",
    "            nonlocal cost\n",
    "            cache[root] = path.copy()\n",
    "            for next in children[root]:\n",
    "                if next != parent:\n",
    "                    path[0] += 1\n",
    "                    dfs(next, root, path)\n",
    "                    path[0] -= 1\n",
    "            \n",
    "            for next in children_reverse[root]:\n",
    "                if next != parent:\n",
    "                    path[1], cost = path[1] + 1, cost + 1\n",
    "                    dfs(next, root, path)\n",
    "                    path[1] -= 1\n",
    "        \n",
    "        dfs(0, -1, [0, 0])\n",
    "        ans = [cost]\n",
    "        for node in  range(1, n):\n",
    "            ans.append(ans[0] - cache[node][1] + cache[node][0])\n",
    "\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        children = defaultdict(list)\n",
    "        children_reverse = defaultdict(list)\n",
    "        for src, dst in edges:\n",
    "            children[src].append(dst)\n",
    "            children_reverse[dst].append(src)\n",
    "        \n",
    "        cache, cost = {}, 0\n",
    "        def dfs(root: int, parent: int, path: List[int]):\n",
    "            nonlocal cost\n",
    "            cache[root] = path.copy()\n",
    "            for next in children[root]:\n",
    "                if next != parent:\n",
    "                    path[0] += 1\n",
    "                    dfs(next, root, path)\n",
    "                    path[0] -= 1\n",
    "            \n",
    "            for next in children_reverse[root]:\n",
    "                if next != parent:\n",
    "                    path[1], cost = path[1] + 1, cost + 1\n",
    "                    dfs(next, root, path)\n",
    "                    path[1] -= 1\n",
    "        \n",
    "        dfs(0, -1, [0, 0])\n",
    "        return list(map(lambda idx : cost - cache[idx][1] + cache[idx][0], range(n)))\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = [set() for i in range(n)]\n",
    "        d = [set() for i in range(n)]\n",
    "        for i,j in edges:\n",
    "            g[i].add(j)\n",
    "            g[j].add(i)\n",
    "            d[i].add(j)\n",
    "        #换根\n",
    "        vis=[False]*n\n",
    "        val = [0]*n\n",
    "        vis[0] = True\n",
    "        def dfs(x):\n",
    "            ret = 0\n",
    "            for y in g[x]:\n",
    "                if not vis[y]: \n",
    "                    vis[y] = True\n",
    "                    ret += dfs(y)\n",
    "                    if y not in d[x]:\n",
    "                        ret += 1\n",
    "            val[x] = ret\n",
    "            return ret\n",
    "\n",
    "        dfs(0)\n",
    "        vis=[False]*n\n",
    "        vis[0]=True\n",
    "        ans = [0]*n\n",
    "        def dfs2(x,fa): \n",
    "            for y in g[x]:\n",
    "                if not vis[y]: \n",
    "                    vis[y] = True\n",
    "                    if y in d[x]:    \n",
    "                        ans[y] = fa+1\n",
    "                    else:\n",
    "                        ans[y] = fa-1\n",
    "                    dfs2(y,ans[y])\n",
    "                     \n",
    "        ans[0] = val[0]\n",
    "        dfs2(0,val[0])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # The graph would form a tree if its edges were bi-directional.\n",
    "        #联通图        \n",
    "        outd=defaultdict(list)\n",
    "        ind=defaultdict(list)\n",
    "        \n",
    "        for a,b in edges:\n",
    "            outd[a].append(b)\n",
    "            ind[b].append(a)\n",
    "        # 每一条有向边 以及反转\n",
    "        #确定从这往后都是往新的点发散需要反转多少条边\n",
    "        goDownCost={}\n",
    "        def edgetoEnd(a:int,b:int,pre:int)->int:\n",
    "            if (a,b) not in goDownCost:\n",
    "                change=pre\n",
    "                for out in outd[b]:\n",
    "                    if out!=a:\n",
    "                        change+=edgetoEnd(b,out,0)\n",
    "                for ins in ind[b]:\n",
    "                    if ins!=a:\n",
    "                        change+=edgetoEnd(b,ins,1)\n",
    "                goDownCost[(a,b)]=change\n",
    "            return goDownCost[(a,b)]\n",
    "                \n",
    "        ans=[-1]*n\n",
    "        for i in range(n):\n",
    "            change=0\n",
    "            for out in outd[i]:\n",
    "                change+=edgetoEnd(i,out,0)\n",
    "            for ins in ind[i]:\n",
    "                change+=edgetoEnd(i,ins,1)\n",
    "            ans[i]=change\n",
    "      \n",
    "        return ans\n",
    "                \n",
    "         \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        t = defaultdict(list)\n",
    "        \n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            t[u].append(v)\n",
    "            t[v].append(u)\n",
    "        \n",
    "        res = [0] * n\n",
    "        f = [0] * n\n",
    "        sizes = defaultdict(list)\n",
    "        \n",
    "        def dfs(p, u):\n",
    "            cnt = 0\n",
    "            sz = 0\n",
    "            \n",
    "            for v in t[u]:\n",
    "                if v == p:\n",
    "                    continue\n",
    "                    \n",
    "                if v not in g[u]:\n",
    "                    cnt += 1\n",
    "                \n",
    "                cnt0, sz0 = dfs(u, v)\n",
    "                sz += sz0\n",
    "                sizes[(u, v)] = sz0\n",
    "                cnt += cnt0\n",
    "            \n",
    "            f[u] = cnt\n",
    "            return cnt, sz + 1\n",
    "        \n",
    "        dfs(-1, 0)\n",
    "        #print(f)\n",
    "        \n",
    "        res[0] = f[0]\n",
    "        \n",
    "        def solve(p, u):\n",
    "            #print('xxx', p, u)\n",
    "            for v in t[u]:\n",
    "                if v == p:\n",
    "                    continue\n",
    "                \n",
    "                utov = 1 if v in g[u] else 0\n",
    "                vtou = 1 if u in g[v] else 0\n",
    "                \n",
    "                res[v] = f[v]\n",
    "                res[v] += utov\n",
    "                left = res[u] - f[v] - vtou\n",
    "                res[v] += left\n",
    "                \n",
    "                #print(u, v, f[v], utov, left)\n",
    "                solve(u, v)\n",
    "        \n",
    "        solve(-1, 0)\n",
    "        \n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import *\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        graph=defaultdict(list)\n",
    "        dirGraph=defaultdict(lambda: defaultdict(int))\n",
    "        for x,y in edges:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "            dirGraph[x][y]=1\n",
    "        os=[0]*n\n",
    "        def dfs(x,fx):\n",
    "            b=0\n",
    "            for nx in graph[x]:\n",
    "                if nx==fx: continue\n",
    "                if not dirGraph[x][nx]:\n",
    "                    b+=1\n",
    "                b+=dfs(nx,x)\n",
    "            os[x]=b\n",
    "            return b\n",
    "        ret=[0]*n\n",
    "        dfs(0,-1)\n",
    "        def dfs2(x,fx,fxb):\n",
    "            xb=os[x]\n",
    "            b=fxb-xb\n",
    "            if fx!=-1:\n",
    "                if dirGraph[fx][x]:\n",
    "                    b+=1\n",
    "                else:\n",
    "                    b-=1\n",
    "            ret[x]=xb+b\n",
    "            for nx in graph[x]:\n",
    "                if nx==fx: continue\n",
    "                dfs2(nx,x,ret[x])\n",
    "        dfs2(0,-1,os[0])\n",
    "        return ret\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        adj, es = defaultdict(list), defaultdict(bool)\n",
    "        for a, b in edges:\n",
    "            adj[a].append(b)\n",
    "            adj[b].append(a)\n",
    "            es[(a, b)] = True\n",
    "        \n",
    "        radj = defaultdict(list)\n",
    "        revs, vis = [0]*n, set()\n",
    "        def dfs1(i):\n",
    "            vis.add(i)\n",
    "            for j in adj[i]:\n",
    "                if j in vis: continue\n",
    "                radj[i].append(j)\n",
    "                revs[i] += dfs1(j)\n",
    "                if not es[(i, j)]:\n",
    "                    revs[i] += 1\n",
    "            return revs[i]\n",
    "        \n",
    "        dfs1(0)\n",
    "\n",
    "        ans = [0]*n\n",
    "        def dfs2(i, c):\n",
    "            ans[i] = revs[i]+c\n",
    "            for j in radj[i]:\n",
    "                d = 1 if es[(i, j)] else -1\n",
    "                dfs2(j, c+revs[i]-revs[j]+d)\n",
    "        \n",
    "        dfs2(0, 0)\n",
    "\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        e = collections.defaultdict(dict)\n",
    "        for x, y in edges:\n",
    "            e[x][y] = 0\n",
    "            e[y][x] = 1\n",
    "        f = collections.Counter()\n",
    "        g = {}\n",
    "        h = set()\n",
    "\n",
    "        def work(k):\n",
    "            h.add(k)\n",
    "            for x in e[k]:\n",
    "                if x in h:\n",
    "                    continue\n",
    "                g[x] = k\n",
    "                f[k] += work(x) + e[k][x]\n",
    "            return f[k]\n",
    "\n",
    "        g[0] = -1\n",
    "        work(0)\n",
    "        print(f)\n",
    "        ret = [0] * n\n",
    "\n",
    "        h = set()\n",
    "\n",
    "        def work2(k, v):\n",
    "            h.add(k)\n",
    "            ret[k] = f[k] + v\n",
    "            for x in e[k]:\n",
    "                if x in h:\n",
    "                    continue\n",
    "                work2(x, v + f[k] - e[k][x] - f[x] + e[x][k])\n",
    "\n",
    "        work2(0, 0)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        edges=[tuple(i) for i in edges]\n",
    "        edges=set(edges)\n",
    "        g=[[] for i in range(n)]\n",
    "        for i in edges:\n",
    "            g[i[0]].append(i[1])\n",
    "            g[i[1]].append(i[0])\n",
    "        \n",
    "        @cache\n",
    "        def dfs(pos,fa):\n",
    "            ans=0\n",
    "            for i in g[pos]:\n",
    "                if i==fa:continue\n",
    "                ans+=dfs(i,pos)\n",
    "                ans+=0 if (pos,i) in edges else 1\n",
    "        \n",
    "        \n",
    "        \n",
    "            return ans\n",
    "    \n",
    "    \n",
    "        ans=[0]*n\n",
    "        for i in range(n):\n",
    "            ans[i]=dfs(i,-1)\n",
    "        \n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        adj = [[] for _ in range(n)]\n",
    "        back = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            adj[x].append(y)\n",
    "            back[y].append(x)\n",
    "\n",
    "        import functools\n",
    "        @functools.cache\n",
    "        def dfs_out(u, p):\n",
    "            res = 0\n",
    "            for v in back[u]:\n",
    "                if v == p: continue\n",
    "                res += 1\n",
    "                res += dfs_out(v, u)\n",
    "\n",
    "            for v in adj[u]:\n",
    "                if v == p: continue\n",
    "                res += dfs_out(v, u)\n",
    "            return res\n",
    "\n",
    "        ans = [0] * n\n",
    "        for i in range(n):\n",
    "            ans[i] = dfs_out(i, -1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class RerootingDP:\n",
    "    def __init__(self, n:int, edges=[], undirected=True):\n",
    "        self.n = n\n",
    "        self.g = [[] for _ in range(n)]\n",
    "        self.undirected = undirected\n",
    "        self.dct = {}\n",
    "        for x, y, w in edges: \n",
    "            self.add_edge(x, y, w)\n",
    "            self.dct[(x, y)] = w\n",
    "            self.dct[(y, x)] = -w\n",
    "    \n",
    "    def add_edge(self, x, y, w):\n",
    "        self.g[x].append((y, w))\n",
    "        self.g[y].append((x, w * 2 * int(self.undirected) - 1))\n",
    "\n",
    "    def get_result(self) -> list[int]:\n",
    "        result, size = [0] * self.n,  [1] * self.n\n",
    "        # ** 专心计算0号节点的结果 **\n",
    "        def dfs(x: int, fa: int, depth: int) -> None:\n",
    "            result[0] += depth < 0  # depth 为 0 到 x 的距离\n",
    "            for y, w in self.g[x]:  # 遍历 x 的邻居 y\n",
    "                if y != fa:  # 避免访问父节点\n",
    "                    dfs(y, x, w)  # x 是 y 的父节点\n",
    "                    size[x] += size[y]  # 累加 x 的儿子 y 的子树大小\n",
    "        dfs(0, -1, 0)  # 0 没有父节点\n",
    "        # ** 只需要考虑相邻节点 x 和 y 的相对关系即可 **\n",
    "        def reroot(x: int, fa: int) -> None:\n",
    "            for y, w in self.g[x]:  # 遍历 x 的邻居 y\n",
    "                if y != fa:  # 避免访问父节点\n",
    "                    result[y] = result[x] - self.dct[(y, x)]\n",
    "                    reroot(y, x)  # x 是 y 的父节点\n",
    "        reroot(0, -1)  # 0 没有父节点\n",
    "        return result\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        edges = [[x, y, 1] for x, y in edges]\n",
    "        rerooting_dp = RerootingDP(n=n, edges=edges, undirected=False)\n",
    "        return rerooting_dp.get_result()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        s = set()\n",
    "        dic = defaultdict(list)\n",
    "        for a,b in edges:\n",
    "            dic[a].append(b)\n",
    "            dic[b].append(a)\n",
    "            s.add((a,b))\n",
    "        @lru_cache(None)\n",
    "        def cal(i,a):\n",
    "            if i == -1:\n",
    "                i = a\n",
    "            if len(dic[a]) == 1 and dic[a][0] == i:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            for k in dic[a]:\n",
    "                if k != i:\n",
    "                    if (k,a) in s:\n",
    "                        ans += 1 + cal(a,k)\n",
    "                    else:\n",
    "                        ans += cal(a,k)\n",
    "            return ans\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            res.append(cal(-1,i))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        \"\"\"\n",
    "        :param n:\n",
    "        :param edges:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = defaultdict(list)\n",
    "        m2 = defaultdict(list)\n",
    "        for i in edges:\n",
    "            m1[i[0]].append(i[1])\n",
    "            m2[i[1]].append(i[0])\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def get_link_cnt(cur, prev= -1):\n",
    "            cnt = 0\n",
    "            for i in m1[cur]:\n",
    "                if i != prev:\n",
    "                    cnt += get_link_cnt(i, cur)\n",
    "            # rev part\n",
    "            for i in m2[cur]:\n",
    "                if i != prev:\n",
    "                    cnt += 1 + get_link_cnt(i, cur)\n",
    "            return cnt\n",
    "\n",
    "        return [get_link_cnt(i, -1) for i in range(n)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        sons = collections.defaultdict(dict)\n",
    "        for a, b in edges :\n",
    "            sons[a][b] = 0\n",
    "            sons[b][a] = 1\n",
    "        \n",
    "        @functools.lru_cache(None)\n",
    "        def solve(s, t) :\n",
    "            to_ret = 0\n",
    "            for t_next in sons[t] :\n",
    "                if t_next == s :\n",
    "                    continue\n",
    "                to_ret += sons[t][t_next]\n",
    "                to_ret += solve(t, t_next)\n",
    "            return to_ret\n",
    "        \n",
    "        to_ret = []\n",
    "        for i in range(n) :\n",
    "            rett = 0\n",
    "            for st in sons[i] :\n",
    "                rett += sons[i][st] + solve(i, st)\n",
    "            to_ret.append(rett)\n",
    "        return to_ret\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
